// 数组中位数
public class FindMedian {
    public static double findMedian(int[] nums){
        if (nums.length % 2 == 1){ // 奇数
            return QuickSelect.quick(nums, 0, nums.length - 1, nums.length / 2);
        }else {                    // 偶数
            int x = QuickSelect.quick(nums, 0, nums.length - 1, nums.length / 2);
            int y = QuickSelect.quick(nums, 0, nums.length - 1, nums.length / 2 - 1);
            return (x + y) / 2.0;
        }
    }

    public static void main(String[] args) {
        System.out.println(findMedian(new int[]{3, 1, 5, 4}));
        System.out.println(findMedian(new int[]{3, 1, 5, 4, 7, 8}));
        System.out.println(findMedian(new int[]{4, 5, 1}));
        System.out.println(findMedian(new int[]{4, 5, 1, 6, 3}));
    }
}
